package com.ycz.algorithm.utils.timecomplex;

import java.util.Arrays;
import java.util.Collections;

/**
 * @author yancz
 * @ClassName TimeComplexUtil
 * @description: 时间复杂度分析
 * 时间复杂度不是指算法的运行时间，而是指算法的运行时间随着数据体量增大的增长趋势
 * @date 2024-08-28 09:29:39
 * @version: 1.0
 */
public class TimeComplexUtil {

    // 算法A，时间复杂度为常数阶
    static void algorithm_A(int n) {
        System.out.println(0);
    }

    // 算法B，时间复杂度为线性阶
    static void algorithm_B(int n) {
        for (int i = 0; i < n; i++) {
            System.out.print(0);
        }
    }

    // 算法C，时间复杂度为常数阶
    static void algorithm_C(int n) {
        for (int i = 0; i < 10000; i++) {
            System.out.print(0);
        }
    }

    // 1.常数阶，输入数据大小与n无关，常数阶算法的时间复杂度为O(1)
    static int constant(int n) {
        int count = 0;
        int size = 10000;
        for (int i = 0; i < size; i++) {
            count++;
        }
        return count;
    }

    // 2.线性阶，操作数量随输入数据大小n呈线性增长，一般出现在单层循环中
    // 遍历数组和链表的时间复杂度都为O(n)，n为数组或链表的长度
    static int linear(int n) {
        int count = 0;
        for (int i = 0; i < n; i++) {
            count++;
        }
        return count;
    }

    // 3.平方阶，操作数量随输入数据大小n呈平方阶增长，一般出现在嵌套循环中
    // 外层循环和内层循环的时间复杂度都为O(n)，总体复杂度即为O(n²)
    static int quadratic(int n) {
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                count++;
            }
        }
        return count;
    }

    // 平方阶典型算法：冒泡排序
    static void bubbleSort(int[] nums) {
        for (int i = nums.length - 1; i > 0; i--) { // 外层循环，未排区间
            for (int j = 0; j < i; j++) { // 内循环，将未排区间的最大元素交换到最右侧
                if (nums[j] > nums[j + 1]) { // 如果前一个元素比后一个元素大，则交换元素
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
    }

    // 4.指数阶算法，一般出现在递归函数中，时间复杂度为O(2ⁿ)
    static int exponential(int n) {
        int total = 0, base = 1;
        for (int i = 0; i < n; i++) { // 外层循环，轮数
            for (int j = 0; j < base; j++) {
                total++;
            }
            base *= 2;
        }
        return total;
    }

    // 以上指数阶算法的递归方式
    // 通常，指数阶算法不适用数据规模较大的情况
    static int expRecur(int n) {
        if (n == 1) return 1;
//        return expRecur(n - 1) + expRecur(n - 1) + 1;
        return expRecur(n - 1) + expRecur(n - 1) + 1;
    }

    // 5. 对数阶算法，每次缩减一半，最后到1的轮数，时间复杂度为O(㏒n)
    static int logarithmic(int n) {
        int count = 0;
        while (n > 1) {
            n /= 2;
            count++;
        }
        return count;
    }

    // 上面对数阶算法的递归方法
    // 对数阶算法常用在分治策略中，增长缓慢，时间复杂度仅次于常数阶算法
    static int logRecur(int n) {
        if (n <= 1) return 0;
        return logRecur(n / 2) + 1;
    }

    // 6. 线性对数阶算法，常出现在嵌套循环中，时间复杂度为O(n㏒n)
    // 快速排序、归并排序、堆排序等主流算法的时间复杂度都为O(n㏒n)
    static int linearLogRecur(int n) {
        if (n <= 1) return 1;
        int count = linearLogRecur(n / 2) + linearLogRecur(n / 2);
        for (int i = 0; i < n; i++) {
            count++;
        }
        return count;
    }

    // 7. 阶乘算法，一般用递归来实现，时间复杂度为O(n!)
    // 当n>=4时恒有n! > 2ⁿ，所以阶乘算法比指数阶算法增长的更快
    // 以下求n的阶乘
    static int factorialRecur(int n) {
        if (n == 0) return 1;
        int count = 0;
        for (int i = 0; i < n; i++) {
            count += factorialRecur(n - 1);
        }
        return count;
    }

    // 获取数字1的索引位，如果返回-1，则无此元素
    // 当1在第一位时，此时达到最佳时间复杂度Ω，对应函数的渐进下界
    // 当1在最后一位时，此时达到最差时间复杂度O，对应函数的渐进上界
    static int findOneElement(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1) {
                return i;
            }
        }
        return -1;
    }

    // 生成一个数据，元素为{1,2,3,...,n}，打乱顺序
    private static int[] randomArray(int n) {
        Integer[] nums = new Integer[n];
        // 生成一个顺序数组，{1,2,3,...,n}
        for (int i = 0; i < n; i++) {
            nums[i] = i + 1;
        }
        // 随机打乱数组元素顺序
        Collections.shuffle(Arrays.asList(nums));
        int[] res = new int[n];
        for (int i = 0; i < nums.length; i++) {
            res[i] = nums[i];
        }
        return res;
    }

    public static void main(String[] args) {
        long t1 = System.currentTimeMillis();
        algorithm_A(100000);
        long t2 = System.currentTimeMillis();
        System.out.println("算法A运行所需时间：" + (t2 - t1) + "ms！");
        long t3 = System.currentTimeMillis();
//        algorithm_B(1000);
        algorithm_B(100000);
        long t4 = System.currentTimeMillis();
        System.out.println();
        System.out.println("算法B运行所需时间：" + (t4 - t3) + "ms！");
        long t5 = System.currentTimeMillis();
//        algorithm_C(1000);
        algorithm_C(100000);
        long t6 = System.currentTimeMillis();
        System.out.println();
        System.out.println("算法C运行所需时间：" + (t6 - t5) + "ms！");
        // 结论：当数据的体量足够大时，时间复杂度为常数阶的算法效率一定优于线性阶的算法效率
        System.out.println(constant(10000));
        System.out.println(linear(10000));
        System.out.println(quadratic(100));
        int[] nums = {23, 4, 67, 6, 9, 10, 12, 34, 12};
        bubbleSort(nums);
        for (int i : nums) {
            System.out.print(i + "\t");
        }
        System.out.println();
        System.out.println(exponential(5));
        System.out.println(expRecur(5));
        System.out.println(logarithmic(32));
        System.out.println(logRecur(32));
        System.out.println(linearLogRecur(2));
        System.out.println("5的阶乘5!=" + factorialRecur(5));
        int[] randomArrs = randomArray(10);
        System.out.println("元素1的索引为：" + findOneElement(randomArrs));
    }


}
